package com.hdu.other.dp.gupiao;

public class lc188 {
    class Solution {
        public int maxProfit(int k, int[] prices) {
            int len = prices.length;
            int[][] dp = new int[k + 1][len];
            for (int i = 1; i <= k; i++) {
                int best = dp[i - 1][0] - prices[0];
                for (int j = 1; j < len; j++) {
                    dp[i][j] = Math.max(dp[i][j - 1], prices[j] + best);
                    best = Math.max(best, dp[i - 1][j] - prices[j]);
                }
            }
            return dp[k][len - 1];
        }
    }
}
